COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\magnification\magstephalf
C00014 ENDMK
C⊗;
\magnification\magstephalf
\input macro.tex
\def\today{\ifcase\month\or
  January\or February\or March\or April\or May\or June\or
  July\or August\or September\or October\or November\or December\fi
  \space\number\day, \number\year}
\baselineskip 14pt
\rm
\line{\sevenrm a33.tex[154,phy] \today\hfill}


%usage: to get erf(x), write $\fnc{erf}(x)$

\bigskip
Let {\sl set function\/} from $S$ to $T$ mean a function whose arguments
are all subsets of~$S$, and whose result is a subset of~$T$. Some examples of
set functions:

\smallskip\halign{\quad\lft{#}\cr
Union: $X↓1∪X↓2=\{\,u\mid u\in X↓1∨u\in X↓2\,\}\quad (S↓1=S↓2=T)$\cr
Intersection:
$X↓1∩X↓2=\{\,u\mid u\in X↓1∧u\in X↓2\,\}\quad (S↓1=S↓2=T)$\cr
Difference:
$X↓1-X↓2=\{\,u\mid u\in X↓1∧u\not\in X↓2\,\}\quad (S↓1=S↓2=T)$\cr
Set Concatenation:
$X↓1\otimes X↓2=\{\,u↓1\otimes u↓2\mid 
u↓1\in X↓1∧u↓2\in X↓2\,\};\quad (S↓1=S↓2=T)$\cr
Set Shuffle: shuffle$(X↓1,X↓2)=\cup$ shuffle$(u↓1,u↓2)\ni
u↓1\in X↓1∧u↓2\in X↓2$.\cr
Concatenative Closure: $X↑{\ast}=
\{\,u↓1\otimes u↓2\otimes \cdots\otimes u↓n\mid
u↓i\in X,\;n≥0\,\};\quad (S=T=\Sigma↑{\ast})$\cr
Arithmetic Sum: $X↓1+X↓2=\{\,u↓1+u↓2\mid u↓1\in X↓1,\;u↓2\in X↓2\,\};\quad
(S↓1=S↓2=T=$ {\bf R})\cr
Topological Closure: $\fnc{Cl}(X)=\{\,u\mid \,\hbox{every open neighborhood 
of $u$ contains an element of $X$}\,\}$,\cr
\qq\qq\qq $(S=T=$ {\bf R})\cr
Constant$↓K(X)=K$, for any fixed set $K$.\cr
Projection$↓i(X↓1,X↓2,\ldots,X↓n)=X↓i$, for any fixed $i\in(1,N)$.\cr}

In general, all boolean functions give rise to set functions akin to
union, intersection, and difference; all functions $S\times S →T$
give rise to set functions akin to set concatenation and arithmetic sum.

A set function is {\sl monotone\/} if putting more elements into any argument
results in more elements (or at least, not losing any) in the result;
$f(X,Y)$ is monotone if $X↓1\subseteq X↓2$, $Y↓1\subseteq Y↓2$ implies
$f(X↓1,Y↓1)\subseteq f(X↓2,Y↓2)$.

\smallskip
\disleft 20pt::
{\bf Drill:} The composition of monotone functions is monotone.

\smallskip
\disleft 20pt::
{\bf Drill:} Confirm all the set functions listed above, except difference,
are monotone. Confirm that a function of several variables is monotone
iff it is monotone in each of the variables separately.

\smallskip
\disleft 20pt::
{\bf Drill:} If $f$ is monotone, is it always true that $X\subseteq f(X)$?

\smallskip
An infinite sequence of sets $\langle X↓1,X↓2,\ldots\rangle$ is {\sl nested\/}
if $X↓i\subseteq X↓{i+1}$. The {\sl limit\/} of a nested sequence of sets
is $X↓{\omega}=\bigcup X↓i$. A monotone set function~$f$ takes nested
sequences of sets $\langle X↓1,X↓2,\ldots\rangle$ and $\langle Y↓1,Y↓2,\ldots
\rangle$ into a nested sequence of sets $\langle f(X↓1,Y↓1),f(X↓2,Y↓2),\ldots
\rangle$. 

Since $X↓i\subseteq X↓{\omega}$, $Y↓i\subseteq Y↓{\omega}$,
$f(X↓i,Y↓i)\subseteq f(X↓{\omega},Y↓{\omega})$, and
$\lim\langle f(X↓1,Y↓1),f(X↓2,Y↓2),\ldots\rangle\subseteq f(X↓{\omega},
Y↓{\omega})$; $f$~is {\sl continuous\/} if equality holds, so that
$\hbox{limit}\langle f(X↓1,Y↓1),f(X↓2,Y↓2),\ldots\rangle =f(X↓{\omega},
Y↓{\omega})$.

\smallskip
\disleft 20pt::
{\bf Drill:} Show union, intersection, concatenation, and concatenative
closure are continuous, but that closure is not.

\smallskip
\disleft 20pt::
{\bf Answer:} Let $X↓i$ be the set $\{1,1/2,1/3,\ldots,1/9\}$; then
$X↓{\omega}=\{1/i\}$; $\fnc{Cl}(X↓i)=X↓i$, limit $\fnc{Cl}(X↓i)=X↓{\omega}$,
but $\fnc{Cl}(X↓{\omega})=X↓{\omega}∪\{0\}$.

\smallskip\noindent
{\bf Theorem:} Let $f$ be a monotone set function. If $f(X)=\bigcup f(Y)$
for the finite subsets $Y\subseteq X$, then $f$~is continuous.

\smallskip\noindent
{\bf Proof.} If $u\in f(X↓{\omega})$, then $u\in f(Y)$ for some finite
subset~$Y$ of~$X↓{\omega}$. Each element of~$Y$ appears in all but
finitely many~$X↓i$, so $Y\subseteq X↓i$ for some~$i$, $u\in f(X↓i)$,
so $f(X↓{\omega})\subseteq\lim f(X↓i)$. We have shown
$\lim f(X↓i)\subseteq f(X↓{\omega})$, so $f(X↓{\omega})=\lim f(X↓i)$.

\smallskip
\disleft 20pt::
{\bf Drill:} Show the conditions of this theorem hold for union, intersection,
set concatenation, and concatenative closure, but not topological closure.

\smallskip
A set $X$ is a {\sl fixed point\/} of a set function~$f$ if $f(X)=X$.
It is a {\sl greatest fixed point (GFP)\/} if every fixed point of~$f$
is a subset of~$X$, and a {\sl least fixed point (LFP)\/} if~$X$ is a
subset of every other fixed point.

\smallskip\noindent
{\bf Theorem:} A monotone set function has a unique least fixed point.

\smallskip\noindent
{\bf Proof.} Let $f$ be a monotone function. Let $C$~(``contracters'')
be the class of sets~$X$ for which $f(X)\subseteq X$, and let
$L$~(``least'') be $\bigcap↓{X\in C}X$, the intersection of all sets
in~$C$. Then 
$$f(L)=f\left(\bigcap↓{X\in C}X\right)\subseteq \bigcap↓{X\in C}
f(X)\subseteq\bigcap↓{X\in C}X=L\,$$ 
so 
$$f\bigl(f(L)\bigr)\subseteq f(L)\,,\;
f(L)\in C\,,\; L\subseteq f(L)\,,\; L=f(L)\,.$$ 
Since any fixed point~$X$
of~$f$ belongs to~$C$, $L\subseteq X$, so $L$~is the least fixed point
of~$f$.

\smallskip\noindent
{\bf Theorem:} A monotone set function has a unique greatest fixed point.

\smallskip\noindent
{\bf Proof.} Let $f$ be a monotone function. Let $E$~(``expanders'')
be the class of sets~$X$ for which $X\subseteq f(X)$, and let
$G$~(``greatest'') be the union of all sets in~$E$.
Then 
$$G=\bigcup↓{X\in E}X\subseteq \bigcup↓{X\in E}f(X)\subseteq f(G)\,,$$
so 
$$f(G)\subseteq f\bigl(f(G)\bigr)\,,\; f(G)\in E\,,\; f(G)\subseteq G\,,\;
f(G)=G\,.$$ 
Since any fixed point~$X$ of~$f$ belongs to~$E$, $X\subseteq G$,
so $G$~is the greatest fixed point of~$f$.

\smallskip\noindent
{\bf Exercise:} Let $f$ be a monotone set function, and $X$ a set for which
$X\subseteq f(X)$. Show there is a unique least fixed point of~$f$
containing~$X$. 

\smallskip\noindent
{\bf Exercise:} Let $f$ be a monotone set function, and $X$ a set for which
$f(X)\subseteq X$. Show there is a unique greatest fixed point of~$f$
contained in~$X$.

\smallskip
\disleft 20pt::
{\bf Drill:} Let $f$ be a monotone set function from $S$ to $S$,
and $g(X)=\overline{f(\overline{X})}$. Show $g$~is monotone, and that its
fixed points are the complements of those of~$f$.

\smallskip\noindent
{\bf Exercise:} Let $f↓Y(X)=\{\epsilon\}∪(X\otimes Y)$, for some fixed
set~$Y$ not containing~$\epsilon$. Show the LFP and GFP of~$f↓Y$
are~$Y↑{\ast}$, so that $Y↑{\ast}$ 
is the unique fixed point of~$f↓Y$.

\smallskip\noindent
{\bf Proof:} If $X$ is a fixed point of $f↓Y$, by induction on~$n$,
$X$~contains $\bigcup↓{i=0}↑nY↑i$, so $Y↑{\ast}\subseteq X$, and
$Y↑{\ast}$ is clearly a~FP of~$f↓Y$, so $Y↑{\ast}$ is the unique LFP of~$f↓Y$.

\smallskip
Let $X$ be a fixed point of $f↓Y$ containing an element $u\not\in Y↑{\ast}$.
Let $u$ be the shortest such element. Since $\epsilon\in Y$, $u≠\epsilon$,
and $u\in XY$, so $u=vw$, $v\in X$, $w\in Y$, $w≠\epsilon$. Then
$\left|v\right|<\left|u\right|$,
$v\in Y↑{\ast}$, so $u\in Y↑{\ast}$, contradiction.

\smallskip
\disleft 20pt::
{\bf Drill:} Show if we omit the condition $\epsilon\not\in Y$, $Y↑{\ast}$~is
still the LFP of~$f↓Y$. What other fixed points are there?





\bigskip
\parindent0pt
\copyright 1984 Robert W. Floyd

First draft November 14, 1984

\bye